This invention relates to error checking, and more particularly, to ways in which to perform cyclic redundancy checking on data packets of variable lengths.
Error-detecting code techniques such as cyclic redundancy checking (CRC) techniques are commonly used in data communications and other applications in which it is desired to check whether data has been corrupted. In a typical scenario, data to be transmitted (called a “message”) is encoded by performing CRC operations. During CRC operations, message bits are processed to generate corresponding parity bits (also sometimes called a CRC checksum). The parity bits are appended to the message bits to form code words.
Each codeword is transmitted over the communications link and is received by appropriate receiver circuitry at a remote circuit. The receiver circuitry performs the same type of CRC calculations on the codewords that were performed at the receiver. The resulting calculations are then evaluated to determine whether the transmitted data has been corrupted. With one approach, the parity bits from the receiver are compared to newly calculated parity bits to determine whether they match as expected. If the CRC operations performed at the receiver reveal that the computed parity bits do not match the parity bits that were transmitted as part of the codeword, then appropriate actions can be taken. For example, the receiver can ask the transmitter to resend the data.
Sometimes CRC functionality is used locally. For example, CRC techniques may be used to check whether data has been corrupted on a local hard disk drive. With this type of arrangement, CRC operations are performed before data is stored in the drive and when the stored data is being retrieved.
To calculate the parity bits for a message, the message bits are treated as the coefficients of a polynomial. During CRC processing, the polynomial is divided by another polynomial called the generator (g) using polynomial division. The remainder of this polynomial division becomes the parity bits.
In low data-rate environments, it is possible to compute parity bits on incoming message bits by processing each bit one at a time. A running value (the accumulator “A”) is computed as each bit is received. After the last message bit has been processed, the value of the accumulator A is equal to the desired remainder (i.e., the desired parity bits).
At higher data rates, it is desirable to handle message bits in batches (bytes), typically of 8 bits. With this type of scheme, the message bits are processed 8 bits at a time. Each 8 bits that are processed result in an update to the value of the accumulator A. When an entire packet of message bits (i.e., an entire message) has been processed, the value of the accumulator represents the parity bits for the message. Because packets of message bits typically have bit lengths that are integral multiples of 8, this type of scheme is generally satisfactory, so long as the data rate is not too high.
At even higher data rates, further increases in CRC throughput are needed. As a results, CRC arrangements have been developed that handle data in larger batches. For example, CRC arrangements have been developed that handle message data in 64-bit (8-byte) batches. When messages have lengths that are multiples of 8 bytes, a single CRC circuit can be used to handle the functions associated with calculating the accumulator A. For example, if a message is 128 bits long, this CRC circuit could make two calculations—one to calculate an initial value of A based on the first 8 bytes and one to calculate the final value of A based on the initial value of A and the next 8 bytes. A message that is 256 bits long could be treated similarly using the CRC circuit to calculate the initial value of A and then updating this value three times using the same CRC circuit.
As the size of the “batch” in which the message bits increases, however, it becomes increasingly less realistic to expect all message to have a length that is an integral multiple of the batch size. Thus it is generally not practical or desirable to require that all messages have a length that is an exact multiple of 64 bits (i.e., only full 64-bit words). This has resulted in the use of special length-dependent CRC circuits, each of which is designed to handle the CRC operations associated with a particular length of data.
In a situation in which CRC operations are performed on eight bytes of the message at a time, it is typically necessary for CRC processing circuitry to include 8 special length-dependent CRC circuits for calculating the accumulator. Each of these eight length-dependent CRC circuits handles a different one of the eight possible message-length scenarios. If the length of the message is an integral number of 64-bit words, a first CRC circuit is used to update the accumulator as the message is processed. If, however, the length of the message is not an integral number of 64-bit words and the end of the message contains a partial word, the message bits in the partial word can be handled by an appropriate one of the remaining CRC circuits. For example, if a partial word at the end of the message contains three bytes of data, a special three-byte CRC circuit may be used to perform the final accumulator update. A partial word can contain anywhere from one byte to seven bytes of data, so seven of the eight length-dependent CRC circuits are used to handle accumulator updating operations in each of these seven conditions.
With this type of parallel CRC arrangement the number of CRC subcircuits that are required to perform CRC operations scales linearly with the number of possible partial word lengths, resulting in the consumption of significant resources.
It would be desirable to be able to handle messages containing partial words more efficiently.